﻿/* 二叉排序树、二叉查找树、二叉搜索树
 *性质：
 * 1 若它的左子树不空，则左子树上的值都小于根结点的值。
 * 2 若它的右子树不空，则右子树上的值大于根结点的值。
 * 3 左右子树也都是二叉排序树。
 *
 */

#ifndef BINARYSORTTREE_H
#define BINARYSORTTREE_H

#include <stddef.h>
#include <vector>

using namespace std;

typedef struct BinarySortTreeNode{
    int data;
    BinarySortTreeNode *left;
    BinarySortTreeNode *right;
    BinarySortTreeNode():data(-1),left(NULL),right(NULL){}
}BSTNode,*PBSTree;

/****************************
 * 二叉排序树相关问题
 ****************************/
//1 当同一个组数据，输入顺序不同构建的二叉排序树相同吗？（相同。）
void TwoTreeCompare();
//2 将一个二叉树转化成二叉排序树（未完成）
void conversion();
/*3 二叉搜索树的后序遍历序列
*输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。
*如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
* 思路：根据二叉树的性质得到，后序遍历（左右根）获得的数组是有规律的，
* 数组最后一项是二叉排序树的根结点，剩下的所有项可以分成两部分，前半部分是左子树（
* 所有结点的值都小于根节点），后半部分（所有结点的值都大于根节点）。
*
*/
void Q3_VerifySquenceOfBSTTest();
bool Q3_VerifySquenceOfBST(const vector<int>&intVtr);
/* 4 二叉搜索树与双向链表(测试函数没通过)
 * 输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。
 * 要求不能创建任何新的结点，只能调整树中结点指针的指向。
 */
void Q4_ConvertTest();
BSTNode *Q4_Convert(BSTNode*root);
void Q4_ConvertRecursion(BSTNode*root,BSTNode *pre);




/****************************
 * 二叉排序树基本操作函数
 ****************************/
// 二叉排序树测试函数
void BinarySortTreeNodeTest();

//创建二叉树
void CreateBSTree(BSTNode**root,const int count);
//向树中插入数据
bool insert(PBSTree *T,int data);
//前序遍历
vector<int> preorderTraverse(BSTNode *root);
//中序遍历
vector<int> InorderTraverse(BSTNode *root);
//后序遍历
vector<int> PostorderTraverse(BSTNode *root);
void PostorderTraverseSub(BSTNode *root,vector<int> *intVtr);
//删除某节点(存在问题)
//bool deleteNode(PBSTree *p);
//bool deleteNodeByKey(PBSTree T,const int &key);
BSTNode  * delBST(PBSTree t, int  key); /*在二叉排序树t中删去关键字为k的结点*/
//查找树中与key相等的结点，*p返回
bool search(PBSTree T,int key,PBSTree root,PBSTree *p);
//计算所有节点数
int NodeCount(PBSTree T);
//销毁
void Destroy(PBSTree *T);
void Destroy_count(PBSTree *T,int *count);

//横向打印
void PrintPBSTree(PBSTree T);
void PrintPBSTreeSub(PBSTree t,int h);

#endif // BINARYSORTTREE_H
